Recent Content

Going Faster with Lisp

posted on 2017-09-17 16:10:00

For the first time in 3+ years, I'm working in earnest on a hobby project.

It feels like coming home, to be writing lisp and blogging again. Once again I'm playing with Nintendo emulation, don't ask why it's captured my imagination so. I'd like to briefly discuss what's brought me back and then we'll talk about what I learned writing lisp today.

My Absence

I haven't really worked on hobby projects since mid 2014. Even then my output was reduced substantially from 2012 when I lived alone and cl-6502/coleslaw had my full attention. I never stopped wanting to learn more, or loving lisp specifically, I just lost the energy to pursue it. That was due to (in rough order): Work, burnout, my relationship, and buying a house. Where burnout == a curiously strong blend of exhaustion, impostor syndrome, and unclear goals. It was scary at times when I wondered if I had lost my passion or commitment but ultimately good for me.

A lot of why I stalled out had to do with my old Nintendo emulator. I had made some bad assumptions, especially about how memory worked, due to not knowing much about systems programming or hardware when I started and didn't want to throw away everything I had to start fresh. cl-6502 had also felt very public so when progress had stalled before even being able to play a game that was quite embarrassing. I also didn't really know about test ROMs until way too late in the going.

But time heals all wounds and I have plenty of ideas. So here we are.

Design Changes

With cl-6502, I just focused on the CPU since that was something I had an inkling of how to approach. My biggest mistake was treating RAM as a 64k element array. The actual Nintendo used Memory Mapped I/O to talk to the graphics and sound cards. The only way to support that in famiclom was to overwrite the routines that read and wrote to RAM in cl-6502. It was unacceptable to me from both a design and performance perspective.

This time around, I'm using a separate object to represent the Memory Map so that when an CPU instruction reads or writes to an address, it'll actually get handled by the right part of the system: the RAM, Video Card, Sound, or cartridge. I'm also going to be focused on using test ROMs through as much of the process as I can. I'll write more about that in a future article but, long story short, TDD is hard to do when writing an emulator.

Lisp, Fast, OO: Pick 3

I managed to get cl-6502 running fast enough last time around but it was still 100x slower than Ian Piumarta's lib6502 written in C. There's no reason that has to be the case, I simply didn't know how to approach optimizing Lisp. I would use SBCL's statistical profiler, sprinkle compiler declarations in my code, re-profile, and pray. Today I'd like to focus on a few tricks for figuring out if declarations are helping or not and getting friendly with your disassembler. I'll also talk a little about why I wound up going with DEFSTRUCT over DEFCLASS.

lol, dis

Profilers are great for helping you figure out what parts of your code you spend the most time in. Once you've identified a function that needs to go fast, the next step is usually to add an optimize declaration. Something like:

(declare (optimize (speed 3) (safety 1))) ; or even (safety 0)

Recompiling the function afterward will result in the compiler printing out notes about what tripped it up while compiling the code. One thing I didn't realize back when I was working on cl-6502 (but seems obvious in retrospect) is that you can include optimize and type declarations in methods too! That said, it can be a pain to constantly write out different optimize and type declarations, recompile, and call disassemble on the code to see differences in the output. Additionally, there is not a portable way to disassemble methods, only their generic functions which is really just the dispatch machinery and not the work that you're interested in.

While Doug Hoyte's book Let Over Lambda is a bit controversial among lispers, he offers some good advice and good tools for remedying these points in Chapter 7. In particular, he supplies a read macro to quickly enable maximum optimization in a method or function and a regular macro to allow testing out type declarations effect on an anonymous function quickly at the REPL. I've taken the liberty of adding both to my .sbclrc file so I have easy access to them when I'm trying things out.

(defun enable-sharpf-read-macro ()
  (set-dispatch-macro-character #\# #\f
    (lambda (stream sub-char numarg)
      (declare (ignore stream sub-char))
      (setf numarg (or numarg 3))
      (unless (<= numarg 3)
        (error "Invalid value for optimize declaration: ~a" numarg))
      `(declare (optimize (speed ,numarg)
                          (safety ,(- 3 numarg)))))))

(defmacro dis (args &rest body)
  (flet ((arg-name (arg)
           (if (consp arg)
               (cadr arg)
               arg))
         (arg-decl (arg)
           (if (consp arg)
               `(type ,(car arg) ,(cadr arg))
               nil)))
    (let ((arglist (mapcar #'arg-name args))
          (declarations (mapcar #'arg-decl args)))
      `(disassemble
         (lambda ,arglist
           (declare ,@(remove nil declarations))
           ,@body)))))

I also dug around to see if there was a way to get disassembly for a single method and found a helpful thread on Google Groups from which I built a little function for disassembling the "fast-function" commonly invoked for a method.

(defun disasm-method (name specializers)
  "E.g. (disasm-method 'package:generic-fun '(class t))"
  (let* ((method (find-method name nil specializers))
         (function (sb-mop:method-function method))
         (fast-function (sb-pcl::%method-function-fast-function function)))
    (disassemble fast-function)))

A "Practical" Example

All code for this section is on the ground-floor branch on Github

Today I was working on memory mappers / cartridges for the NES emulator. Let's look at how I used these tools to optimize a method on the simplest mapper NROM. (Used in titles like Donkey Kong and the original Super Mario Brothers.) The method we'll be looking at is called load-prg. Put simply, it takes an address and loads a byte from the PRG section of the game cartridge.

Since any game will load data from the cartridge a lot we really want this to be a fast operation. And since it's loading from a static array, we would hope we can get this down to a handful of assembly instructions. Here's my initial implementation:

(defmethod load-prg ((mapper nrom) address)
  (let ((rom (mapper-rom mapper)))
    (if (= 1 (rom-prg-count rom))
        (aref (rom-prg rom) (logand address #x3fff))
        (aref (rom-prg rom) (logand address #x7fff)))))

You can see it takes an NROM mapper and an address and, based on the number of PRG banks in the cartridge, does a little math on the address and accesses the PRG with AREF. Let your eyes skim over the unoptimized disassembly:

CL-USER> (disasm-method #'clones.mappers::load-prg '(clones.mappers::nrom t))
; disassembly for (SB-PCL::FAST-METHOD CLONES.MAPPERS:LOAD-PRG
                   (CLONES.MAPPERS::NROM T))
; Size: 280 bytes. Origin: #x2290E8F5
; 8F5:       498B4C2460       MOV RCX, [R12+96]               ; no-arg-parsing entry point
                                                              ; thread.binding-stack-pointer
; 8FA:       48894DF8         MOV [RBP-8], RCX
; 8FE:       498B5805         MOV RBX, [R8+5]
; 902:       48895DE0         MOV [RBP-32], RBX
; 906:       8D43FD           LEA EAX, [RBX-3]
; 909:       A80F             TEST AL, 15
; 90B:       0F85F3000000     JNE L11
; 911:       8B4B01           MOV ECX, [RBX+1]
; 914:       4881F903FD5020   CMP RCX, #x2050FD03             ; #<SB-KERNEL:LAYOUT for CLONES.ROM:ROM {2050FD03}>
; 91B:       0F85C8000000     JNE L10
; 921: L0:   488B531D         MOV RDX, [RBX+29]
; 925:       BF02000000       MOV EDI, 2
; 92A:       E8411C1FFF       CALL #x21B00570                 ; GENERIC-=
; 92F:       488B5DE0         MOV RBX, [RBP-32]
; 933:       488B75E8         MOV RSI, [RBP-24]
; 937:       4C8B45F0         MOV R8, [RBP-16]
; 93B:       7456             JEQ L5
; 93D:       488B4B0D         MOV RCX, [RBX+13]
; 941:       8D46F1           LEA EAX, [RSI-15]
; 944:       A801             TEST AL, 1
; 946:       750A             JNE L1
; 948:       A80F             TEST AL, 15
; 94A:       7542             JNE L4
; 94C:       807EF111         CMP BYTE PTR [RSI-15], 17
; 950:       753C             JNE L4
; 952: L1:   488BFE           MOV RDI, RSI
; 955:       40F6C701         TEST DIL, 1
; 959:       7407             JEQ L2
; 95B:       488B7FF9         MOV RDI, [RDI-7]
; 95F:       48D1E7           SHL RDI, 1
; 962: L2:   4881E7FEFF0000   AND RDI, 65534
; 969:       8D41F1           LEA EAX, [RCX-15]
; 96C:       A80F             TEST AL, 15
; 96E:       7519             JNE L3
; 970:       8B41F1           MOV EAX, [RCX-15]
; 973:       2C85             SUB AL, -123
; 975:       3C74             CMP AL, 116
; 977:       7710             JNBE L3
; 979:       488BD1           MOV RDX, RCX
; 97C:       B904000000       MOV ECX, 4
; 981:       FF7508           PUSH QWORD PTR [RBP+8]
; 984:       E9AFEDA1FD       JMP #x2032D738                  ; #<FDEFN SB-KERNEL:HAIRY-DATA-VECTOR-REF/CHECK-BOUNDS>
; 989: L3:   0F0B0A           BREAK 10                        ; error trap
; 98C:       36               BYTE #X36                       ; OBJECT-NOT-VECTOR-ERROR
; 98D:       08               BYTE #X08                       ; RCX
; 98E: L4:   0F0B0A           BREAK 10                        ; error trap
; 991:       41               BYTE #X41                       ; OBJECT-NOT-INTEGER-ERROR
; 992:       30               BYTE #X30                       ; RSI
; 993: L5:   488B4B0D         MOV RCX, [RBX+13]
; 997:       8D46F1           LEA EAX, [RSI-15]
; 99A:       A801             TEST AL, 1
; 99C:       750A             JNE L6
; 99E:       A80F             TEST AL, 15
; 9A0:       7542             JNE L9
; 9A2:       807EF111         CMP BYTE PTR [RSI-15], 17
; 9A6:       753C             JNE L9
; 9A8: L6:   488BFE           MOV RDI, RSI
; 9AB:       40F6C701         TEST DIL, 1
; 9AF:       7407             JEQ L7
; 9B1:       488B7FF9         MOV RDI, [RDI-7]
; 9B5:       48D1E7           SHL RDI, 1
; 9B8: L7:   4881E7FE7F0000   AND RDI, 32766
; 9BF:       8D41F1           LEA EAX, [RCX-15]
; 9C2:       A80F             TEST AL, 15
; 9C4:       7519             JNE L8
; 9C6:       8B41F1           MOV EAX, [RCX-15]
; 9C9:       2C85             SUB AL, -123
; 9CB:       3C74             CMP AL, 116
; 9CD:       7710             JNBE L8
; 9CF:       488BD1           MOV RDX, RCX
; 9D2:       B904000000       MOV ECX, 4
; 9D7:       FF7508           PUSH QWORD PTR [RBP+8]
; 9DA:       E959EDA1FD       JMP #x2032D738                  ; #<FDEFN SB-KERNEL:HAIRY-DATA-VECTOR-REF/CHECK-BOUNDS>
; 9DF: L8:   0F0B0A           BREAK 10                        ; error trap
; 9E2:       36               BYTE #X36                       ; OBJECT-NOT-VECTOR-ERROR
; 9E3:       08               BYTE #X08                       ; RCX
; 9E4: L9:   0F0B0A           BREAK 10                        ; error trap
; 9E7:       41               BYTE #X41                       ; OBJECT-NOT-INTEGER-ERROR
; 9E8:       30               BYTE #X30                       ; RSI
; 9E9: L10:  488B512D         MOV RDX, [RCX+45]
; 9ED:       4883FA04         CMP RDX, 4
; 9F1:       7E11             JLE L11
; 9F3:       488B4125         MOV RAX, [RCX+37]
; 9F7:       81781103FD5020   CMP DWORD PTR [RAX+17], #x2050FD03  ; #<SB-KERNEL:LAYOUT for CLONES.ROM:ROM {2050FD03}>
; 9FE:       0F841DFFFFFF     JEQ L0
; A04: L11:  0F0B0A           BREAK 10                        ; error trap
; A07:       0A               BYTE #X0A                       ; OBJECT-NOT-TYPE-ERROR
; A08:       18               BYTE #X18                       ; RBX
; A09:       23               BYTE #X23                       ; 'CLONES.ROM:ROM
; A0A:       0F0B10           BREAK 16                        ; Invalid argument count trap

WOOF! 280 bytes of assembly, including a full CALL to a generic equality test, and two JMP instructions to other functions. Even without knowing any assembly, this seems like an awful lot of junk just for a measly array lookup! I think one valuable insight I got from Chapter 7 of Let Over Lambda was to disregard what I thought I know or didn't about assembly and just use my damn eyes. Doesn't this seem like a silly amount of code? Let's crank the optimization up:

(defmethod load-prg ((mapper nrom) address)
  #f
  (let ((rom (mapper-rom mapper)))
    (if (= 1 (rom-prg-count rom))
        (aref (rom-prg rom) (logand address #x3fff))
        (aref (rom-prg rom) (logand address #x7fff)))))

As soon as I recompiled this code, I got 6 notes from the compiler stating that it wasn't confident about the return value of (rom-prg-count rom) hence the generic equality test. It also wasn't confident what kind of array (rom-prg rom) was or if all the elements even shared a type! That will cause AREF to be slow. Even so, the generated assembly drops to 116 bytes since the #f read macro expands to a declaration with maximum speed (3) and minimum safety (0). It should go without saying that you only want to do this in code that A) really needs to be fast and for which, B) you're very confident about who will call it and how. Here's the disassembly:

CL-USER> (disasm-method #'clones.mappers::load-prg '(clones.mappers::nrom t))
; disassembly for (SB-PCL::FAST-METHOD CLONES.MAPPERS:LOAD-PRG
                   (CLONES.MAPPERS::NROM T))
; Size: 116 bytes. Origin: #x2290F6CB
; 6CB:       48895DF0         MOV [RBP-16], RBX               ; no-arg-parsing entry point
; 6CF:       488B4605         MOV RAX, [RSI+5]
; 6D3:       488945F8         MOV [RBP-8], RAX
; 6D7:       488B501D         MOV RDX, [RAX+29]
; 6DB:       BF02000000       MOV EDI, 2
; 6E0:       E88B0E1FFF       CALL #x21B00570                 ; GENERIC-=
; 6E5:       488B5DF0         MOV RBX, [RBP-16]
; 6E9:       488B45F8         MOV RAX, [RBP-8]
; 6ED:       7528             JNE L1
; 6EF:       488B500D         MOV RDX, [RAX+13]
; 6F3:       488BFB           MOV RDI, RBX
; 6F6:       40F6C701         TEST DIL, 1
; 6FA:       7407             JEQ L0
; 6FC:       488B7FF9         MOV RDI, [RDI-7]
; 700:       48D1E7           SHL RDI, 1
; 703: L0:   4881E7FE7F0000   AND RDI, 32766
; 70A:       B904000000       MOV ECX, 4
; 70F:       FF7508           PUSH QWORD PTR [RBP+8]
; 712:       E9E166A2FD       JMP #x20335DF8                  ; #<FDEFN SB-KERNEL:HAIRY-DATA-VECTOR-REF>
; 717: L1:   488B500D         MOV RDX, [RAX+13]
; 71B:       488BFB           MOV RDI, RBX
; 71E:       40F6C701         TEST DIL, 1
; 722:       7407             JEQ L2
; 724:       488B7FF9         MOV RDI, [RDI-7]
; 728:       48D1E7           SHL RDI, 1
; 72B: L2:   4881E7FEFF0000   AND RDI, 65534
; 732:       B904000000       MOV ECX, 4
; 737:       FF7508           PUSH QWORD PTR [RBP+8]
; 73A:       E9B966A2FD       JMP #x20335DF8                  ; #<FDEFN SB-KERNEL:HAIRY-DATA-VECTOR-REF>

A Fork in the Road

Those two JMP instructions and the generic equality CALL are still in the assembly though as you can see from the comments on the right hand side. Why? Because we didn't actually resolve any of the compiler's uncertainties about the code. We have to help it know what type of values it will be working with. The question is how to best do that. One way would be to just add a bunch of local type declarations in the method:

(defmethod load-prg ((mapper nrom) address)
  #f
  (let* ((rom (mapper-rom mapper))
         (prg (rom-prg rom))
         (prg-count (rom-prg-count rom)))
    (declare (type byte-vector prg)
             (type fixnum prg-count))
    (if (= 1 prg-count)
        (aref prg (logand address #x3fff))
        (aref prg (logand address #x7fff)))))

That will work and does generately substantially nicer code (82 bytes and no CALLs or JMPs). But boy, it forced us to completely restructure the method and, well, the new version feels a bit disjointed. The declarations stick out and distract from the underlying ideas. The alternative is to try and teach the compiler what types are returned by the accessor functions we're using to pull data out of the ROM. And this is where we come to the important difference about DEFCLASS and DEFSTRUCT from where I'm sitting as an emulator author.

Optimizing with Structs is Easier

(Ed. note 09/19/2017: Rainer Joswig left a very informative comment about Structs vs Classes and Optimizing with CLOS on reddit.)

Getting struct-related code to go fast is easier for a very specific reason. Both DEFCLASS and DEFSTRUCT allow you to optionally specify the types of their slots. Unfortunately, DEFCLASS does absolutely no optimization with this information, while DEFSTRUCT treats it as a guarantee and propagates it through the auto-generated slot accessors and, therefore, the rest of your code.

Now there's a good reason for this and I am certainly not advocating for using DEFSTRUCT by default. The reason is that DEFSTRUCT is not designed to be interactively redefined or changed at runtime unlike most of the language. DEFCLASS could have the types of its slots (or even the slots themselves) change at any time including runtime and so it isn't reasonable for it to treat the type declaration as a fact.

DEFSTRUCT has other downsides as well, including auto-generating a bunch of symbols in the current package among other things. It's clunkier to work with in several ways than DEFCLASS but for truly performance intensive stuff, the type declaration behavior makes it worth it from where I'm sitting. Just don't default to DEFSTRUCT in general. This message from the Rob Warnock Archive may also prove interesting.

This is something I always had questions about though and it was compounded a bit due to the fact that DEFSTRUCT is barely mentioned by Practical Common Lisp or Common Lisp Recipes. Practical Common Lisp is still the best way to learn the language in my opinion. I also honestly enjoy the things that are in the Common Lisp standard due to history but I'd never quite found an answer to "When should I use structs vs classes?" that I liked. Hopefully future lispers will be able to stumble on these notes (or parse the spec better than I did).

Modifying the ROM definition

Here's what our ROM struct looks like with the added type declarations:

(defstruct rom
  (pathname    nil :read-only t)
  (prg         #() :read-only t :type byte-vector)
  (chr         #() :read-only t :type byte-vector)
  (prg-count     0 :read-only t :type ub8)
  (chr-count     0 :read-only t :type ub8)
  (mirroring   nil :read-only t)
  (mapper-name nil :read-only t))

The previous version had no :type options and the default values were all nil. After changing the struct and recompiling, we can write the same version of load-prg as before but get much better generated assembly since the compiler knows the types returned by the struct accessors (and thus the array element type):

(defmethod load-prg ((mapper nrom) address)
  #f
  (let ((rom (mapper-rom mapper)))
    (if (= 1 (rom-prg-count rom))
        (aref (rom-prg rom) (logand address #x3fff))
        (aref (rom-prg rom) (logand address #x7fff)))))

; disassembly for (SB-PCL::FAST-METHOD CLONES.MAPPERS:LOAD-PRG (CLONES.MAPPERS::NROM T))
; Size: 90 bytes. Origin: #x22910BDE
; BDE:       488B4005         MOV RAX, [RAX+5]                ; no-arg-parsing entry point
; BE2:       488B501D         MOV RDX, [RAX+29]
; BE6:       4883FA02         CMP RDX, 2
; BEA:       7528             JNE L2
; BEC:       488B400D         MOV RAX, [RAX+13]
; BF0:       F6C101           TEST CL, 1
; BF3:       7407             JEQ L0
; BF5:       488B49F9         MOV RCX, [RCX-7]
; BF9:       48D1E1           SHL RCX, 1
; BFC: L0:   4881E1FE7F0000   AND RCX, 32766
; C03:       48D1F9           SAR RCX, 1
; C06:       0FB6540801       MOVZX EDX, BYTE PTR [RAX+RCX+1]
; C0B:       48D1E2           SHL RDX, 1
; C0E: L1:   488BE5           MOV RSP, RBP
; C11:       F8               CLC
; C12:       5D               POP RBP
; C13:       C3               RET
; C14: L2:   488B400D         MOV RAX, [RAX+13]
; C18:       F6C101           TEST CL, 1
; C1B:       7407             JEQ L3
; C1D:       488B49F9         MOV RCX, [RCX-7]
; C21:       48D1E1           SHL RCX, 1
; C24: L3:   4881E1FEFF0000   AND RCX, 65534
; C2B:       48D1F9           SAR RCX, 1
; C2E:       0FB6540801       MOVZX EDX, BYTE PTR [RAX+RCX+1]
; C33:       48D1E2           SHL RDX, 1
; C36:       EBD6             JMP L1

Finally, we can improve things just a bit by promising that the address we call the load-prg method with will be an unsigned 16-bit value since the 6502 only has a 64k address space:

(defmethod load-prg ((mapper nrom) address)
  #f
  (declare (type ub16 address))
  (let ((rom (mapper-rom mapper)))
    (if (= 1 (rom-prg-count rom))
        (aref (rom-prg rom) (logand address #x3fff))
        (aref (rom-prg rom) (logand address #x7fff)))))

; disassembly for (SB-PCL::FAST-METHOD CLONES.MAPPERS:LOAD-PRG (CLONES.MAPPERS::NROM T))
; Size: 66 bytes. Origin: #x22910DDE
; DDE:       488B4005         MOV RAX, [RAX+5]                ; no-arg-parsing entry point
; DE2:       488B501D         MOV RDX, [RAX+29]
; DE6:       4883FA02         CMP RDX, 2
; DEA:       751C             JNE L1
; DEC:       488B400D         MOV RAX, [RAX+13]
; DF0:       4881E1FE7F0000   AND RCX, 32766
; DF7:       48D1F9           SAR RCX, 1
; DFA:       0FB6540801       MOVZX EDX, BYTE PTR [RAX+RCX+1]
; DFF:       48D1E2           SHL RDX, 1
; E02: L0:   488BE5           MOV RSP, RBP
; E05:       F8               CLC
; E06:       5D               POP RBP
; E07:       C3               RET
; E08: L1:   488B400D         MOV RAX, [RAX+13]
; E0C:       4881E1FEFF0000   AND RCX, 65534
; E13:       48D1F9           SAR RCX, 1
; E16:       0FB6540801       MOVZX EDX, BYTE PTR [RAX+RCX+1]
; E1B:       48D1E2           SHL RDX, 1
; E1E:       EBE2             JMP L0

Updates

(Ed. note 09/19/2017: Some additional speedups have been made since this article was published.)

Paul Khuong was kind enough to note that SBCL was unable to hoist the (logand address xxx) computation out of the conditional. This duplication can be seen in the disassembly from the two MOV .. AND .. SAR .. MOVZX blocks. Doing so improved the assembly a bit further to 51 bytes. Reflecting on it further, I realized there's no need for a conditional expression at all!

In NROM cartridges, they can either have 1 or 2 PRG banks each of which are 16k. Because the 6502 has a 64k address space and the cartridge data begins at 32k, an NROM cartridge with only 1 PRG bank doesn't actually fill the address space. In our load-prg method, we just want to make sure that if we're given a higher address like 54321 that we wrap that around to not run off the end of our 16k worth of PRG. To do that, we can just logical AND the address with (1- (length array)).

Doing that eliminates the branch and results in a nice, lean 40 bytes for our final disassembly:

(defmethod load-prg ((mapper nrom) address)
  #f
  (declare (type ub16 address))
  (let* ((rom (mapper-rom mapper))
         (end-of-rom (1- (length (rom-prg rom))))
         (wrapped-address (logand address end-of-rom)))
    (aref (rom-prg rom) wrapped-address)))

; disassembly for (SB-PCL::FAST-METHOD CLONES.MAPPERS:LOAD-PRG (CLONES.MAPPERS::NROM T))
; Size: 40 bytes. Origin: #x22844CCE
; CE:       488B4005         MOV RAX, [RAX+5]                 ; no-arg-parsing entry point
; D2:       488B500D         MOV RDX, [RAX+13]
; D6:       488B52F9         MOV RDX, [RDX-7]
; DA:       4883EA02         SUB RDX, 2
; DE:       4821D1           AND RCX, RDX
; E1:       488B400D         MOV RAX, [RAX+13]
; E5:       48D1F9           SAR RCX, 1
; E8:       0FB6540801       MOVZX EDX, BYTE PTR [RAX+RCX+1]
; ED:       48D1E2           SHL RDX, 1
; F0:       488BE5           MOV RSP, RBP
; F3:       F8               CLC
; F4:       5D               POP RBP
; F5:       C3               RET

Wrap Up

There's a lot of work left to do on the (new) emulator but I'm writing code again, having fun, learning, and using lisp and that's the most important part to me. If you made it this far, thanks for reading. Let me know what you think and happy hacking!

Labor Day Link Fixup

posted on 2017-09-04 11:18:00

Ancient History

For whatever reason, yesterday seemed a good day to decommission Linode 18032 that I bought way back in February of 2009 and had been using to run redlinernotes.com ever since. I bought redlinernotes.com in June 2007 in the wake of my first serious breakup (with Sonya Z) but ran it out of my parents basement up until getting the linode.

Ever since, though my knowledge increased, I didn't bother revamping the linode other than one reinstall with Ubuntu 12.04 when I first migrated my blog away from Wordpress to Coleslaw. I've been gradually moving my online presence towards kingcons.io and making plans to get back to blogging in earnest the past few weeks. But even though kingcons.io was made with (semi-workable) ansible roles, redlinernotes.com was still a big hand rolled minefield with years of digital detritus to boot. Nothing like a 3 day weekend to clean out your digital woodshed.

A Fresh Start

After deleting a lot of crap, I moved the statically hosted documents over to kingcons.io, added an nginx vhost, swapped the DNS over, and nuked the old linode. There was one last thing to do though. When I moved over to coleslaw from Wordpress years ago, I didn't bother fixing up the old links. So I have a bunch of ".post" documents in my blog's git repo that reference expired wordpress links to other posts (like "blog/?p=1234") instead of the slug coleslaw would assign the post.

I guess I didn't care enough at the time or was too focused on coleslaw itself to worry about "legacy content". But I found a wordpress XML backup and figured I might as well fix up the dead links today while I was at it. All while rolling my eyes at dealing with XML.

Link Fixup

Since coleslaw is designed to be backed by git as a content store, I started by grepping through the blog posts to get a list of all the old wordpress post IDs I linked to.

grep -Eo "redlinernotes.com/blog/\?p=(\d+)" *.post | cut -d "?" -f 2

Armed with that, I could tackle digging into the wordpress XML backup to map the post IDs to coleslaw generated titles. Shinmera has been writing stupid amounts of good lisp code over the past few years including Plump, an XML parser. I never completely gelled with CXML back in the day so I figured I'd give plump a go. The following assumes you have a decent lisp installed (I heartily recommend SBCL) and quicklisp.

(ql:quickload 'coleslaw)
(ql:quickload 'plump)

;; Make sure to use a pathname (the #p) for this, plump will treat a plain string as XML to be parsed, not a file.
(defvar *wp-xml* #p"/Users/brit/projects/linode-retirement/wordpress.2010-09-14.xml")

(defvar *doc* (plump:parse *wp-xml*))

I was actually stumped here for a bit because I used a string instead of a pathname as the argument to PARSE and it took me a few minutes querying and getting no results before I looked in the slime inspector and realized the doc hadn't parsed as expected. Once I had this though, it was pretty straightforward to build a hash of IDs to titles...

(defvar *posts* (plump-dom:get-elements-by-tag-name *doc* "item"))

;; For those wondering, :test #'equal is there so we can use string keys. Read Practical Common Lisp or google to learn more.
(defvar *post-id-map* (make-hash-table :test #'equal))

(defun extract (key node)
  (let ((value (first (plump-dom:get-elements-by-tag-name node key))))
    (plump:text value)))

;; Yes, I'm using a private coleslaw function here but I wrote coleslaw so ... uh ... do what I want! 
;; And in case you were wondering, handler-case is lisp's try/catch equivalent and I'm pretty much doing "rescue nil" here.
(defun fixed-title (title)
  (handler-case (coleslaw::slugify title)
    (simple-error () :junk)))
               
(loop for post in *posts*
      do (let ((title (extract "title" post))
               (id (extract "wp:post_id" post)))
           (setf (gethash id *post-id-map*) (fixed-title title))))

And now we're good to update the existing posts to have proper relative links to the content we actually want.

(ql:quickload 'cl-ppcre)

;; Can you tell I did all this in one repl session and just copy pasted it into this blog post?
(coleslaw::load-config "/Users/brit/projects/improvedmeans/")
(coleslaw::load-content)

;; Cute sidenote, since ppcre turns this regex into to a tree of closures which SBCL compiles, this can be #'disassemble-d.
;; Also, it's pretty fast.
(defvar *wp-url-regex*
  (cl-ppcre:create-scanner "w{0,3}?\.?redlinernotes\.com/blog/\\?p=(\\d+)"))

(defstruct counts
  (invalid-slug   0 :type fixnum)
  (post-not-found 0 :type fixnum)
  (updated-url    0 :type fixnum))

(defvar *results* (make-counts))

(defun invalid-slug-p (slug)
  (or (null slug)
      (every #'digit-char-p slug)))

(defun mismatch-p (slug)
  (let ((key (make-pathname :directory '(:relative "posts")
                            :name slug :type "html")))
    (null (gethash key coleslaw::*site*))))

(defun slug-for-match (text start end match-start match-end reg-start reg-end)
  (declare (ignore start end))
  (let* ((id (subseq text (aref reg-start 0) (aref reg-end 0)))
         (match (subseq text match-start match-end))
         (slug (gethash id *post-id-map*))
         (new-url (concatenate 'string "blog.kingcons.io/posts/" slug ".html")))
    (cond ((invalid-slug-p slug)
           (incf (counts-invalid-slug *results*))
           (format t "Couldn't find valid slug for post id: ~d~%" id)
           "/&")
          ((mismatch-p slug)
           (incf (counts-post-not-found *results*))
           (format t "Not found in site content: ~A~%" slug)
           "/&")
          (t
           (incf (counts-updated-url *results*))
           (format t "Replacing ~A with ~A~%" match new-url)
           new-url))))

(coleslaw::do-files (path "/Users/brit/projects/improvedmeans/" "post")
  (let* ((text (alexandria:read-file-into-string path))
         (updated-post (cl-ppcre:regex-replace-all *wp-url-regex* text #'slug-for-match)))
    (with-open-file (out path :direction :output :if-exists :supersede)
      (format out "~A~%" updated-post))))

(format t "~%~%===RESULTS===~%")
(dolist (type '(invalid-slug post-not-found updated-url))
  (let ((symb (alexandria:symbolicate 'counts- type)))
    (format t "~A: ~D Posts~%" type (funcall symb *results*))))

And there you go. A few links are still broken but things are generally improved, I'm down to 1 linode instead of 2, and I had a bit of fun on a lazy Sunday.

===RESULTS===

INVALID-SLUG: 18 Posts

POST-NOT-FOUND: 7 Posts

UPDATED-URL: 58 Posts

In Memoriam

posted on 2017-07-26 07:36:00

I had a dream last night but don't remember much of it. I was the commander of a small starship I think. I don't know if we were civilian or military. I spent some time speaking to staff and checking various stations. And then the new recruits started arriving, nervous and eager. I think Owings was there welcoming them with me.

At some point, as the arrivals became distracted with idle chat, I flipped on the engines with a switch. They hummed to life and we all felt the ship rise slightly beneath us, rocking slightly, our hearts in our throats. A number of recruits shifted to regain their balance. The room fell quiet. I smiled and woke up.

The only part of the dream that matters is that brief moment of floating. Before the voyage really starts. Before we know each other.

I know it's silly but it can still be important.

I believe in what we did at The Iron Yard.

Sheik Scrub

posted on 2015-09-18 15:48:00

The First Year

It's funny that Melee has been a hobby of mine for 2 years and I'm just starting to learn the game. I started getting serious like many do, saw footage of pro players and immediately started practicing tech skill against CPUs.

Then I spammed that tech skill against other scrub friends that also were just learning about the world of SHFFLing. Literally just throwing out moves that are cool in place and hoping the opponent runs into them half the time.

Jump forward 12 months and I've spent a lot of time having fun practicing platform movement, gotten a basic grasp of the hitboxes, knockbock, and lag times of moves for a half dozen characters, and still have no idea how to play.

I became aware that I was practicing tech wrong, I could repeatedly execute techs but not combine them fluidly in combat.

And I was still hopping between characters based on whoever felt good that day though mostly mained Sheik with occasional bursts of Marth or Fox.

The Second Year

Then, I started recording matches semi-regularly but was disappointed at how much my play varied from day-to-day. I still didn't go to locals. And on some level, I still thought my tech was the problem.

Somewhere along the way, I decided that the measure of my progress would be how badly I could beat my only practice partner. I expected to be able to 3 and 4-stock him consistently just as soon as I could get my tech down. You can imagine how that went.

My practice sessions shifted towards working on fluid movement, and more reactionary, thoughtful punishes. I finally settled on Sheik at some point, mostly because it "feels" right.

That said, Max and I still played a lot of Fox and Falcon dittos. He was still the only person I played against. Our play starts to look like two beginners, two bad players, as opposed to just clueless. Baiting starts to become part of my play, I try to recognize and think about neutral. But I still go back and forth with Max.

His punishes have gotten better, his movement is fluid, but more importantly he's thoughtful and adaptive. But I didn't see that. I wasn't pulling ahead, and I was salty about it.

Recent Developments

Then, about 3 months back, after a particularly bad night of salty runbacks I decide to change my relationship with Melee. I had been beating myself up for not being substantially better than Max out of thin air.

I thought about the hours I'm putting in and berated myself for not being better than Max already. But what am I really doing to get better? And if I'm not enjoying it, why play?

The Iron Yard was in between semesters so on a whim, and at the advice of various Melee folks, I watched Ping Pong. Skeptical that I'd like it, I plowed through it in 2 days.

Two things jumped out at me about my relationship with Melee:

  1. My mindset was terrible.
  2. My efforts were unfocused and misdirected.

Who do you play Melee for?

Some days I just had fun playing Melee, no pressure. More often than I'd like to admit, I got salty when I lost. I didn't want to acknowledge and respect my opponent. And that's not intended as a slight against Max.

It's more that I didn't want to have think about why I was losing, or what I could do about it, what I was prepared to do. I wanted to semi-mindlessly play and get acknowledgement for knowing how to do some flashy things. Hell, half the time I would make myself play when I wasn't in the mood because I'd put in so many hours that I should be able to just "turn it on".

I said all kinds of unreasonable things to myself about melee. And I gotta say, playing to win is a piss-poor goal. These days, I'm playing to have fun and to learn. I don't want to be the best. But I want to get better. And I'm going to have to lose. A lot.

Winning begins with seeing your opponent, and the game, as a system that you may not understand but have to respect.

A Man without a Plan ...

For a long time, to the extent I had goals and a plan to achieve them, it was to practice tech skill and flashy platform movement until somehow I just won.

Now, I'm looking at situations where I fail, finding bad habits and coming up with meaningful alternatives to them.

I'm playing competitively via netplay with new people. People who I win and lose to. People who I learn from. And I'm planning to go to locals every once in a while.

I'll keep it up as long as I feel like it. I'll do it as long as it's rewarding. There really are two goals:

  1. Get good enough at Melee to make it out of pools at a local.
  2. Practice being mindful during the game, respectful of my opponent, and kind to myself.

On Expectations and Guilt

I didn't think consciously about my goals in Melee for a long time. I think a big part of that was because I was, for whatever reason, fighting a difficult internal battle with another goal.

Namely, I didn't want to write code as a hobby anymore. I already wrote plenty of code at work and didn't want all my time to be staring into a screen.

But I felt subconscious guilt about this for a long, long time. At some point, I was telling myself I would drop Melee when I was less burned out on programming. But it wasn't burnout.

I never learned to practice or study hard. Partially, that's because I never learned to be kind to myself when I wasn't good at something. I'm learning that now since I'm priviliged to help others struggling to learn to program.

I've spent a large portion of my life tortured by expectations that I largely invent for myself. I've thought of my worth as being tied to meeting those expectations, and being recognized for it. I've worried about being rejected by those I love for not performing, or for not demonstrating my worth.

A huge part of this year for me has been trying to change that mindset. And explore how to live for whatever enriches me, and brings me joy. So far, that's meant more Melee, some ping pong, reflective conversations with dear friends, more time outside, and faith that I can teach my students a bit about the craft of programming. If I'm lucky, I just might love myself yet.

The Right Thing

posted on 2015-05-09 03:35:00

I've been programming for 8 years now. Only half that time professionally. It seems like a long time to me but is a drop in the bucket compared to many in this industry.

If I had to pick two big lessons from the past 8 years to tell someone getting into Software Development for the first time, I would probably say:

  1. Software is never finished.
  2. Software is never "right".

Software is Never Finished

Software is never finished because it exists in a social context. Software is an accessory to daily life and life changes. As our needs evolve, and the context around software shifts, so must the software itself.

Not to mention the fact that the teams working on software and the organizations around it shift. We cannot forget Conway's Law!

I often cannot imagine how the Software industry will ever settle with regards to tools and practices, when I see our tumultuous past 50 years. But even if our techniques and tools settle, I don't imagine our codebases will.

Software is Never "Right"

You might imagine that this section is redundant. Certainly it sounds similar to "Software is Never Finished". But I mean something different. I mean that there isn't a single right way that all software should be written or made.

The internet would lead you to believe otherwise. Programmers are nothing if not evangelists, even zealots, about their tools and techniques, their pet styles and practices, their esoterica.

The most important thing you can do is ignore this. Ignore the hate, Ignore the hype. Do not second guess yourself.

Tools, practices, and domains of knowledge are just that. Even if Software wasn't a moving target (see: Never Finished), we still do not have a single methodology understood to always produce the ideal code. Indeed, there isn't some ideal code we're after. The code is not the most important part, it's just the part we're paid to obsess over.

So don't sweat the folks who insist everyone should follow their "better" way. At the end of the day, good documentation and happy customers are probably more important than most particulars of your codebase.

By all means, don't stop learning and write the best code you can. But chart your own path through our tangled maze of lore. And remind yourself that it's okay to be an average programmer. We've got to find time for families and lives, after all. Speaking of which ...

The Right Thing

It's tough to try to plan for retirement. I'm still too young to think confidently on decade plus time scales.

It's tough to decide how to teach my students and gauge assignments. It's tough to decide what to learn next to become better at programming. It's tough to decide what I want from my career, how to nourish it and have it nourish me. It's tough to decide what's worth doing in general, when our lives are so busy and full.

But there's one decision I make that's really easy, even when it makes my life harder.

It's coming up on six years since Dad died. I cannot measure the amount I've grown since then. I know he'd be proud. But I'm proud and that's even more important. The biggest lesson I learned from John Glenn is probably this:

Loving other people is so obviously the right thing.

I cannot think of a time when I am as confident in my decisions as when I am loving and supporting others.

I'm not proud of my programming skills or code, though cl-6502 is kind of neat. I'm not proud of my job or relationship, though I am thrilled with those aspects of my life.

I'm proud that I handle hard situations with all the grace I am able. I'm proud that I treat others with respect and care because I didn't used to.

Most importantly, I'm proud that when I see someone struggling, I love them.

We do not get to have many easy decisions in our adult lives. But loving those around us, pleasant or unpleasant, in good times or bad is an enormous undertaking. I certainly fail at it, but I never regret it.

It's unfortunate that with our busy lives, in the sea of our alerts and notifications, it is so difficult to focus on the simple and important things. But I truly believe loving others is the most important thing that I do.

I have failed many times before and in many ways and modalities. I have character flaws. I have shortcomings. But if I have helped those around me through difficult periods in their lives and supported them when they were in need? Well, then it's all probably worth it.

Confronting Impostor Syndrome

posted on 2015-03-10 19:57:00

For the bulk of my professional career as a software developer, I've felt like a fraud. To some extent, I think various aspects of tech hiring practices and tool fads/fetishes in the software industry create or exacerbate this feeling in most of us.

I read Joel Spolsky's Java Schools article way back when, before I was really programming. I looked down on Web Dev for a long time. I played with lisp, played with emulation. ... But I've been a professional web dev. Why am I fighting it and being hard on myself for not being a systems programmer?

I flogged myself for some time, a little voice in my head saying that web devlopment "isn't real programming". I would flog myself for not being good at web development when I hadn't embraced it. I would flog myself for not being knowing systems programming when I haven't put any time into it.

Sure, there's plenty I still don't know. But "I don't know but I can figure it out" is the right instinct to have. Trying a bunch of stuff and not finishing is vastly better than paralysis. Exploring any ecosystem and building better apps is better than misguided elitism.

I'm a hacker, through and through. I want to learn, want to improve, want to synthesize new things from my understanding, grow, share, and change. I looked up to the hackers of lisp lore and AI Labs. But that hero worship has become negative, is distracting me from just building things.

Part of the reason that little voice is in my head (and I listened to it for so long) is because I thought I didn't have a chance in this industry.

I've been a successful developer for years but often unable to enjoy my jobs because I've been too uncomfortable to embrace them. Then feared I'll be found out as a fraud, not a "real programmer".

I've been telling my students that since they understand the major components in web development and have some understanding of how they fit together, their real focus to grow should be practice. Constantly building bigger things, trying to make each piece more cleanly than in the past, gradually knowing how to solve harder and harder problems.

I stopped taking my own advice at some point. It's time to build new things again. Bigger things. Not the prettiest or the best, but real.

Goals for 2015: Recreational

posted on 2015-02-21 15:18:00

Recreation and Balance

For years, I've been focused on production. Even my "relaxing" activities aside from throwing dinner parties or going to concerts with friends have been productive in nature.

  • Open Source
  • Trying to Make Music
  • Pseudo-Competitive Smash Brothers Melee

You get the idea. For the past 5 years or so, I've been terrible at doing things purely for recreation and fun. I struggle not to think of it as "wasting time". I'm always anxious about my technical abilities, my ability to find employment, my preparedness for the future. Rationally, I know that's all pretty ridiculous but I struggle to unwind all the same.

Work life balance has for a while seemed a relic of a bygone era. But I want to turn that around this year. Ironically, I've worked more 50 and 60+ hour weeks this year than any previous one. It turns out becoming responsible for the education of 15 people in a 12-week programming bootcamp is pretty demanding. That's why I'm listing these purely recreational goals to try and commit myself to doing some things just for fun.

Recreational Goals

Reading

  1. The Causal Angel by Hannu Rajaniemi
  2. Saga by Brian K. Vaughan
  3. One of Idoru or Pattern Recognition by William Gibson
  4. One of Redemption Ark by Alistair Reynolds or The Player of Games by Iain Banks
  5. Prince of Persia journals
  6. One of Transmetropolitan / Y: The Last Man

Gaming

  1. Retro/Kickstarted: Hyper Light Drifter
  2. New Adventure: One of Rime or Legend of Zelda Wii U
  3. Nostalgia: One of Ocarina of Time, Fez, or Pokemon Red/Blue
  4. Sci-fi: One of SW: KoToR or Mass Effect
  5. Fantasy: Final Fantasy III or Chrono Trigger or Final Fantasy IX or Earthlock
  6. Magic: Play more Magic the Gathering with James, spend money on cards. Be a kid.

Visual

  • Watch at least 2 documentaries about creative passions: Cooking, Indie Games, etc
  • Citizenfour
  • Outerlands?
  • Game Loading?
  • Mind of a Chef?
  • No Map for these Territories?
  • One of Modulations / Hi-Tech Soul

Vacation

  • Take at least one trip to the beach for no less than 5 days.
  • Take at least one trip to see: James, Burke, or Justin.

Goals for 2015: Technical

posted on 2015-01-01 18:15:00

Technical Goals

I've been in a technical rut for a while. Sure, I learned new things at my job but limited myself outside of it by sticking to projects I wasn't motived about and only working with tools I was familiar with.

As much as anything, 2015 is going to be about playing with new projects, experimenting with new tools, and focusing on fundamentals again. Seeing as I have 3 big goals here, I might just try to tackle one each semester. :)

Ocaml

To that end, my primary goal will be to learn Ocaml and build something cool with it. I'm leaving that just as open ended as it sounds.

I'm interested in Ocaml for a variety of reasons. Its origin dates from a time before Intel and Microsoft created a 20-year dominant platform. It was envisioned as a systems language, much like Lisp, to compete with C++.

That said, it employs pattern matching and a strong, static type system like Haskell. Unlike Haskell, it has a fairly simple runtime and compiler built to give very clear intuition about code performance. While Ocaml is strongly functional, it provides for use of imperative state without monad machinations (sorry @James).

There are other reasons but I think this is a good start. I'd be interested in everything from writing an IRC bot, to scripting tasks, to NES reverse engineering tools (i.e. lots of graph manipulation), to OpenMirage toys.

Javascript / Frontend

I've leaned towards backend work in my career where possible. After helping TA Tim's Frontend engineering course last semester I finally want to pick up some front end skills. I'm not angling to get much better from a design or HTML/CSS perspective, but have a definite interest in mithril and Clojurescript's om. Elm also seems really cool but I'd prefer to stick to slightly less alien tech for the time being.

I'm considering porting my Nintendo emulator to Clojurescript and getting it to use canvas but I worry about getting bogged down as I did with the Lisp version. It was fairly painless getting a rough cl-6502 port up in Clojurescript in a few days though.

Algorithms

To be honest, my algorithms chops have never been terribly good. I think one thing that's intimidated me working on trowel is a lack of confidence in my algorithmic reasonining. So I'll be working through the latest edition of Sedgewick's Algorithms with a particular focus on graphs. With any luck I'll actually make some progress on trowel. Maybe I'll even wire it to an om app with some logic programming or constraint propagation tricks.

Goals for 2015

posted on 2015-01-01 17:50:00

2014 was a huge year. Notably, I moved in with Norma, switched jobs from writing code to teaching how to code, and learned more about how to manage myself.

I've got plenty of things to work on in 2015 so I'm breaking this into a sequence of posts based on subject. I'd like to broadly note that for my first semester (roughly January through March) I might barely get anything done and that is okay. I've never taught before and I expect that learning curve to take up most of my time until early April. Now without any further ado ...

A Few Goals for 2015

  1. Personal (forthcoming)
  2. Technical
  3. Musical (forthcoming)
  4. Competitive (forthcoming)
  5. Recreational

Starting Again

posted on 2014-11-30 21:20:00

A Fresh Start

I've been struggling a lot this year. I got stuck in a hole and it took me a while to find my way out. But I learned a few things along the way and I'm very excited about what's coming next.

I've accepted a job as a Ruby on Rails instructor at The Iron Yard. I'll be training people to become engineers in a very short timespan. For over a year, I've been whispering now and then about an interest in teaching, to Norma and friends. Starting January 5th, I'll have my first students. I'm equal parts nervous and exhilarated. I can't wait.

Learning How to Quit

A lot of my happiness and self-worth is tied up in making visible progress on things I care about. Over the past 10 months I lost faith in what I was doing at work and enthusiasm for my personal projects. Rather than recognizing that I should find a job I was passionate about or spend time on projects that excited me, I dug my heels in. No longer.

At one point, I said a Nintendo emulator was my forever project. I'd still like to see it taken further but I'm not going to work on that now. Belligerently sticking to those guns has been limiting my own potential. The only purpose of personal projects is to learn and to grow. They are mine and no one else's.

So until further notice, the emulator is on the backburner. Coleslaw will still get maintenance work but probably not much feature development. There are new things I'm fired up about and my focus will be on deriving as much momentum from them as possible.

Going Forward

I'm playing with Renoise and trying to pick up some music theory. I'm still not really making songs but I'll get there. I'm continuing to learn melee and now that I have a real training regiment in place I'm seeing much faster improvement. Hopefully I'll make it out to local tournaments every now and then.

I want to become more structured about practice. That includes starting to chip away at the stacks of CS and programming books I own that I haven't gotten around to reading. And experimenting with new tools like Ocaml, OpenMirage, and Ansible. And making room for play where nothing gets done.

I need to learn how to love and care for myself in spite of how much I get done, in spite of visible progress made or unmade. Part of that is going to be taking back my online presence, away from the more cultivated space of the last few years. There's a lot I want to accomplish over the next year or so. I'm sure plenty of what I learn won't be according to plan. But it's time to get going. It's time get organized. It's time to dig in.


Unless otherwise credited all material Creative Commons License by Brit Butler