Making PISC faster: Exercises in de-stupiding code

I’ve been reflecting on the various bits of side-project work I’ve done in 2017. One of the most memorable side-projects was a set of optimizations to make PISC not completely slow. It’s still not properly fast, since PISC is currently implemented as the stack-based equivalent to an AST-walking interpreter. However, it is now at a reasonable speed, rather than an incompetent one. The inspiration for my first pass at benchmarking PISC came from this talk about implementing a compiler for K-Lambda Scheme using Rust. There was a specific benchmark from the talk that stuck out to me:

(defun build (counter list)
    (cond 
        ((= 0 counter) list)
        ( true (build ( - counter 1)
             (cons counter list)))))
(build 100000)

In the talk, Siram noted that the compiled-to-rust from K-lambda version of that code took 7 minutes to run. I was very curious to see if PISC would do any better, especially since it can lean on Go’s runtime, rather than performing the rather large amount of copying in the Rusty Runtime. I translated this to two PISC programs, one testing allocation/iteration speed, the other testing the current limits of tail-recursion (something that PISC doesn’t currently optimize for).

: build ( counter list -- list )
    :list :counter
    $counter 0 = 
        [ $list ] 
        [ $counter 1 - { $counter $list } build ] 
    if ;


: build-loop ( counter list -- list )
    :list :counter
        [ $counter 0 = not ] 
        [ { $counter $list } :list $counter 1 - :counter ] 
    while ;

: cons-test ( -- ) 
        # "Code took" is prefixed by time ATM.
        ${ [ 100000 <vector> build-loop ] time " for loop version" } print
        ${ [ 100000 <vector> build drop ] time " for recursive version" } print
;

When I started out, this code was taking upwards of 1.5 minutes to run in the tail-recursive form, and >30 seconds for the looped version. While still faster than the 7 minutes for the K-lambda version, seemed painfully slow for a mere 100,000 list allocations, especially when both Lua and various Scheme implementations could do it in subsecond times. After a late night benchmarking and looking for hot spots, the looped version runs subsecond, and the tail-recursive version runs in 3-10 seconds. (Note 1)

The improvements came from 3 changes focusing on reducing the repeated effort in resolving a string to a piece of executed code.

The first major overhead was in using regular expressions to differentiate integers and doubles from other tokens. This led to a lot of time getting spent in evaluating regex functions, as the way things were set up, a regex would get run over each token every time the relevant piece of code is evaluated. For 0 100 [ 1 + ] times, this would result in both 1 and + having a regex run over them 100 times. Talk about interpretation overhead! Cleaning this up lead to about a 40% runtime reduction for both versions of the code.

The second overhead was by far the biggest, and still isn’t 100% removed: PISC has to perform name resolution on each token it parses. This process currently involves 14 string comparisons, and 4 hashtable table lookups. Before the time spent on optimizing the name resolution process was repeated every time a token was executed. Caching the results of this lookup into function pointers doubled speed of the PISC interpreter in the list building benchmarks. I haven’t been able to get this 100% completed, as I had some mutability and lack of sleep related difficulties in caching the right data for avoiding iterating over quotations and comments when a quotation in re-executed, but this has yet to come up as a hotspot in practice, though I could see it happening. (Note 2)

The third overhead affected function calls and tail-recursion a fair amount: earlier versions of PISC used defer to reset the state of the code quotation being executed after it was finished. This happened every time a PISC definition/quotation was executed. This meant that the cost of defer was getting added to every function call, which was vigorously stressed by tail-recursive code. Using the classic process of splitting a recursive call into recursive and initial forms allowed me to eliminate the use of defer here, which also cut down greatly on the costs of function calls.

Other small improvements have included converting heavily used PISC words from having PISC-heavy defintions to doing most of their work in Go. This included ++, --, as well as the various dictionary utility words, such as -> and <-.

Overall, this puts PISC in the within an order of magnitude of CPython (though python still handles recursive calls better, and is far more mature), and within spitting distance of Go-based Lua implementations, though PISC still doesn’t hold a candle to C-based Lua. As things currently stand, I’m happy with where the performance is for now. PISC needs improvement in other areas (like some kind of module system that isn’t just the PISC version of #include). At some point, I’ll probably start comparing it to TCL, or get a burr in my saddle, and will sit down to try to finish the work I started in removing the evaluation of comments in then AST, as well as finishing out as much reduction in name resolution as I can get away with.

Notes

1) Recursion in Go

I discovered an interesting aspect of the Go runtime in the tail-recursive list builder. Apparently, on 64-bit systems, Go allows up to 1GB memory to be taken up by stack space. This limit is closer to 250MB on 32 bit machines, but is interesting as a demonstration of the unique characteristics of the Go runtime.

2) Problems in handling quotations and comments

There are currently an aspect to how PISC handles quotation-like words, and comments that I don’t care for, but haven’t found the time to fix (yet. Unless someone volunteers a patch, which is very unlikely, though very welcome, it’s something I’ll be taking care of in 2018):

20 [ ${12 43} /* Comment here. */ ] times 

This code will copy the ${, 12, 43 and } tokens into a new code quotation for each iteration of the loop body, as well as having to iterate over the tokens in the comment each time. To be fair, this code is already allocation heavy, so it’s going to be a poor idea for a hot loop, but I’d love to clean this up.

Post Mortem of Ludum Dare 38 and Bullet Surfing

Post Jam version. :)

Ludum Dare is a 3 times a year game jam hosted on ludumdare.com. You can read the rules here if you’re not familiar. This post is a reflection on how the previous one went.

Pre-weekend

Last week I had the unexpected pleasure of taking part in Ludum Dare 38. Up until about the Thursday before, I had been planning on skipping this LD, but I knew I’d be watching the IRC and discord channels for LD, since so much cool stuff shows up in them. Hanging out in there, as well as the realization that I didn’t have any major commitments that particular weekend convinced me to give Ludum Dare 38 a shot. I went into the weekend with 3 things: A minor head cold, a half-baked idea around a pause/teleport/repeat bullet hell game, and knowing that I would not be done in time for Compo (solo, 48 hours) due to the cold.

This meant that I had 72 hours to come up with something I could show to other jammers, which was a nice relaxed pace compared to LD 34, when I went for Compo, but still enough to keep me going.

Friday night/Early Saturday morning

The first minor snag in my plans was that theme I had planned a little round, “Pausing Has Consequences”, was not chosen. Instead, the theme was “Small World”. Still, I had the idea of a Bullet-Hell style game floating around in my head, I just need to figure out how to sorta fit one into the idea of a small world. I also had to face the fact that I wasn’t going to have artistic and musical help, like I had on LD 37 (my friend had school related stuff at the time).

I had other engagements that kept me from seeing the IRC chat at the theme announcement itself, (something I recommend for first time LDers) so around the time that I saw the theme at 1:30 AM and started thinking about it, I didn’t have much energy for the creative side of stuff. Thankfully, there is non-creative work that goes into a video game. Due to the artistic constraints, I decide that I’d take a shot at doing a game with Atari Vector style graphics, in the vein of BattleZone and Asteroids. I’ve played these games on an Atari CD game in the early ‘00s, and even today they have some charm. So the two less creative things I did were find a font that imitated the Atari Vector font, finding the stylish HYPERSPACE font. The other thing that I ended up doing at the time was importing basecode from my LD 37 entry, Fateful Caverns.

6 hours later, Saturday afternoon and evening

After some sleep, and some more time waking up a bit slowly due to the head cold, I started working out what do with this game. Previously I had done Omega Llama for LD 34, and I thought that the Llama would be a great fit for a new game based on trying to survive a bullet hell, and would be a good fit for the vector style graphics I was aiming to produce. In order to make it a loose fit for the small world theme, I decide to locate this game on a single planet, as opposed to the flotilla that hosted the first Omega Llama.

As another upgrade on the first Omega Llama, I decided to add a starfield effect, which was the first bit of game tech that I got up and running, and that’s when I started taking screen recordings of my progress:

The first recording of the game. I was still considering making a boss based bullet hell game.

After the starfield, it took me only maybe 15 minutes to add in a planet. A current little inefficiency is that the stars behind the planet are still rendered, which is something I’d change in a full release of this game, but has yet to be fixed. Sharing this planet drew on attention on IRC, due to how smooth it was compared to the usual fare of chunky pixels. A way for this game to stand out, I suppose.

And that was about as far as I got on Saturday.

Sunday

This was my first shot at doing a “Boss”. I was still thinking on the level of a single enemy here. My original conception would be for a boss based on a vector art style Tiki Shaman that attacked you with Bongos. This was a very rough first pass.

Not quite the first look that the player had (it stared out as a line), but pretty close. After some feedback from the LD discord, I oped for a more menacing, angular head. The rest of the boss would never quite get the same treatment.

This is also as good a time as any to point out that none of the art was done in a program. This is all line/circle/square/ellipse commands using Love2D’s graphics system. I learned a bit about doing that sort of art from this. 1) lines are the easiest thing to freestyle when you’re playing with coordinates. 2) Rectangles are probably the wrong idea at this level. Case in point: The llama (which you’ll see below) was about 2x easier than the boss

This is the start for the Llama, just a rectangle and a few lines.

The Llama neck, head, and ears are a single unbroken line segment, which ends up looking rather cool.

Finally, add a tail, and have it swing a bit more than the rest of appendage. At this point I was also starting to try to figure out a dash/bash move, so that the llama would have a way to attack the boss.

Thanks to some help from the LD discord, I rediscovered the atan2 function, which allowed me to get the shield direction correct. Also, it is now looking like a shield, rather than a ram.

This is as far as I went down the line of having the attack be a bash. I’m just testing out colors and how the dash feels to be a bash.

A reminder that things moving in a straight line can outline circles if they move with periodicity.

I was still thinking of this like a bullet hell, and I thought it would be kinda cool to get some health from using a dash to go through the bullets. So here you can see me playing like a dev, taking damage on purpose, and then regaining it via the dash.

A short clip of using a circle to visualize how the hit geometry looks for the shield. Why a circle? Because that math is much simpler than non AABB rectangles.

This is the first recored bullet surfing that I did. It’s not quite as smooth at it could be, but it illustrates the concept nicely. It was when I did this experiment that I decided against doing a bullet hell game, and decided to base it around collecting them on a combo instead.

At this point, it’s not a boss, it’s a crystal, and the combo mode has been prototyped.

To make it a bit easier to bounce back from a dropped combo (and as a test to see if it might make an interesting powerup), I added a slow to the bullet travel speed when a combo is dropped after you set a record.

In a final push on Sunday evening, I updated the title screen and tried to fix up a few other things. This GIF was my original post the LD website, at about 12:45-1:00AM Eastern. This upload was mostly that I had something up in the event of not being able to add anything else to the game.

Monday, after work

That circle isn’t important, is it? This was the first stab at adding the second, counter-balancing mechanic to the bullet collecting: The Circles of Combo Ending.

It’s in this state, with basic surfing, keyboard controls, movement glitches, good sfx, poorly fitting music, and a slow server to submit to, that I finally put Omega Llama in: Bullet Surfing up onto LD with all of it’s core bits in place, even as buggy as it is.

Thursday

It wouldn’t be a Ludum Dare for me, however, if I didn’t take a least a few hours to try and polish off a least a few of the remaining rough spots.

After a few days of taking a breather, I came back and poked for feedback on the LD discord channel. One thing that ieyfo and Arctodus both agreed on was that while the game was fun, it would be much better with analog controls, rather than digital ones. At first, I took a stab at doing so with a mouse, but that did not turn out very well:

The problem here is that part the balance of the game is that the player can not stop moving while in shield mode. The mouse controls here were just a quick test, but they didn’t turn out very well.

What did end up working excellently, however, was using a game pad. That made the game about 2-4x more fun to play, in part because a game pad lends itself to swervey-smooth looking movement.

So what are a few things I’ve learned from this? ShareX does a pretty decent job of recording GIFs on Windows. Love2D is still awesome. I can now easily work with GamePads, pitch-shifted sounds, and have a way to use vector art. The style of Lua programming that I used in Fateful Cavern, which involved creating separate lua files for each general system in the game, and then using require() to have them communicate with each other seems to work decently well, as I never felt I was in a mire of inescapable spaghetti. Not that I didn’t have bugs that weren’t removed by the end of the Jam, but the code stayed comprehensible.

Next LD, I don’t know what I’ll end up doing, but I’d like play with either lovebpm from rxi, or build a game that uses a camera system so that I can learn how best to work with those, and grow beyond the single-screen experiences I’ve been throwing together the past few times.

Peace out, Fellow Jammers

Lobste.rs

Hacker news is a daily habit for my novelty seeking brain. Most hacker news discussions rarely seem to allow you to get to know the commenters very well. Discussions threads bounce cacophonously between multiple commenters, multiple threads talking past each other. On posts that don’t have that chaotic discussion, there are only a few comments. This isn’t to say that conversations on Hacker news are without value, just that they are impersonal. Hence, it stays as a source of links and what “The Hacker News” has to say about things.

Lobste.rs is like a small hackerspace, compared to HN’s startup enthused sky-scraper. On Hacker News, I’ve often seen interesting projects, such as the Oil Shell, Mu, or Leiningen, where on Lobste.rs, I’ve been able to actually meet the people behind said projects. This is still possible on HN, but much less likely, just due to the volume of people that discuss things there. Those conversations lead to things like learning how to use GDB(which for this Go/C# dev, is not something I commonly use), or the means of interacting with mailing lists, or cracking a cipher for a hackathon, or discussing the various differences between different implementations of virtual machines, interpretors and programming languages.

Facilitating much of this discussion is #lobsters, a companion IRC chatroom to the news site itself, which hosts quite a fun crowd of people. Also enticing is Lobster’s tightened focus on technology, rather than the mushy hodgepodge of loosely tech and startup related news on HN. The only downside of the smaller community is that it does generate less links per day compared to HN, so I still end up reading both, since my appetite for reading can be rather large depending on the day.

Greetings Netizens

First, an explanation. I don’t write quite as often as I might like at Jungle Coder, as writing there often happens out of an inspiration, rather than habit. I do write there as the fancy strikes me, but without regularity or consistency. But I will be saying something here on a weekly basis, planning on Thursday nights. Here, I sacrifice quality and heavy consideration for candor and consistency.

TL;DR This blog updates on Fridays

What could you expect? As the much less formal companion to Jungle Coder, some programming rants, discussion around video games, cooking, video games, poetry, memes, or whatever else strikes my fancy on a given week. Since the aim of this is to write more, I will aim to do a minimum of 250 words per entry, with an ideal entry around 500 words. This post will be a bit longer due to this introductionary bit.

TL;DR I’ll ramble here for about 500 words a week

With that introduction out of the way, onto a ramble:

Tools for thinking and analysing

PowerShell, Regex, Excel, Vim, SQL, Awk, LinqPad, Markdown. Each of these bits of software helps me solve problems. Each of these tools seems a bit like a mental lever once you get past the learning curve. And, for someone like me that prefers to avoid writing excessive code for a problem, as well as avoiding busywork, these tools have been very handy.

The first time I even came close to saving time from a bit of programming, it was using PowerShell to search for a document that my brother had misplaced. PowerShell has also allowed me to write very useful and flexible bits of automation for my work, such as a script for backing up databases, or one that reports to our team chat regarding remaining disk space. The only two things that PowerShell isn’t as good at: It runs a bit slow, and it is only really useful on Windows. If it had full Linux/OSX_{cos bash kinda sucks} support, I’d be using it there.

Regex, especially in Sublime Text (or any editor that highlights matches as they are found), since it allows you to build a very simple templated approach to regular data. In fact, a text editor with Regex for Find/Search is the best place to experiment with such things. They become very useful in other places, such as for parsing specific date-time formats that the standard library for $YOURCURRENTLANG may or may not support.

Excel, because SUM(C:C) and other aggregates on cell ranges make for quick work of basic number crunching. This makes for easy budgeting, and all the what-if analysis it’s known for. The only thing I don’t like about Excel is that it doesn’t integrate very well with other tools (like Regex or Vim), to my knowledge, but often I don’t need it too. Excel is also about the fastest way I currently know to visualize data, whether for science, business, or pleasure _{If you’re a spreadsheet fancier}.

Vim is a mental lever for two reasons: Firstly, and I’d argue pretty importantly, Vim is a Universal Editor Passport. It is the home away from home of editors. I can easily Vim in the Visual Studio high rises, in the concrete jungle that is Eclipse, the funky downtown of IntelliJ, even the Ivory Tower that is EMACS. Sojourning surreptiously to strange servers for supreme justice? Vim is there. Configuring a Raspberry Pi via Super Shell Helper (SSH)? Vim is there too. Secondly, learning the Vim editing model gives you a supremely command-line and laptop friendly keyboard tool-set. This means that not only can you travel to many and varied territories, but your ability to use portable hardware whilst doing so is multiplied.

LinqPad (or the scripting environment of your choice. I’m working on PISC, but python/ruby if that’s your thing), because sometimes Regex isn’t quite enough. Sometimes I just need to generate a bit of data, or do a one-shot on some boiler-plate code, or test an API. LinqPad is great for this, and I’ve been finding PISC to have some utility in the same area. When examining Elder Data from outer planes, it helps to have your own incantations for summoning aviary, nootropic, or (as show below) fishy abominations, knowing that it said enchantments can be easily twisted and warped as needed:

1 :i # You stand as one
${  # Lay the circle
    "!(" { 55 [  # The Elder's number is 55, so it must be.
    ${ "($" $i " ~ /NA/)" } ++i ] # Chant "NA", and  
            #so increase yourself, tO Be StONG
    times  } " && " str-join " # J0in w1th the 0TH3RS!
) { print $0 }" # HE IS THE ZEROTH
} # @#Ei$jasd% AWKTHULU COMES!! LKJALHWER 

Markdown, because it gives the just the right amount of formatting to think in, but enough flexibility to express yourself well. Or at least it gets out of the way for a good ramble.

- FIN -