Up to Main Index Up to Journal for June, 2019
JOURNAL FOR THURSDAY 20TH JUNE, 2019
______________________________________________________________________________
SUBJECT: You asked for an improved matcher…
DATE: Thu 20 Jun 18:10:04 BST 2019
It’s been a while since my last entry, however I’ve not been idle — I’ve been
busy quietly working away on WolfMUD. A number of people have commented on the
matcher and pointed out that it wasn’t up to my usual standards. It was
described to me as “a blob of code that’s hard to decipher”. I whole heartedly
agreed with that assessment and decided to do something about it.
Initially the matcher was a hastily hacked together experiment. As the
experiment seemed quite successful I ran with the code, attempting several
times to clean it up and improve performance. No dice. What it really needed
was a complete overhaul, a rewrite — now that the requirements were better
understood.
The rewrite was completed within a few evenings. However, performance was
horrendous compared to the original and there was still some ugliness in the
code. I persevered, convinced I was on the right track and doing the right
thing. I then spent my evenings over the next week iterating over the new
code. A small tweak here and there, benchmark, repeat. Benchmarking takes
about 2-3 minutes each time, you can’t do anything except sit and wait so as
not to skew the results.
The new matcher makes heavy use of filtering slices without allocating. This
is where you reuse the backing array of the slice you filtering as you iterate
over it:
subset := results[:0]
for _, r := range results {
if r.Test() {
subset = append(subset, r)
}
}
results = results[:len(subset)]
Here the subset slice is reusing the backing array of the results slice. It
does mean that the original content of results will be overwritten.
The final result is… interesting. Performance is mostly improved and I’ve
reduced allocations in a lot of instances. For an idea of the current
performance here are some benchmarks:
name old time/op new time/op delta
MatchAll/#00-4 13.3ns ± 0% 5.2ns ± 0% -61.18%
MatchAll/apple-4 1.46µs ± 2% 1.76µs ± 2% +20.65%
MatchAll/ball-4 1.63µs ± 1% 1.73µs ± 2% +5.97%
MatchAll/token-4 1.44µs ± 1% 1.73µs ± 0% +20.80%
MatchAll/all_ball-4 3.28µs ± 0% 2.08µs ± 1% -36.63%
MatchAll/all_green_ball-4 3.42µs ± 1% 2.23µs ± 1% -34.90%
MatchAll/all_red_ball-4 3.43µs ± 1% 2.22µs ± 1% -35.31%
MatchAll/all_small_ball-4 3.47µs ± 2% 2.20µs ± 3% -36.51%
MatchAll/all_large_ball-4 3.44µs ± 1% 2.21µs ± 2% -35.83%
MatchAll/apple_ball_chalk-4 5.93µs ± 3% 6.05µs ± 1% +1.96%
MatchAll/apple_all_ball_chalk-4 7.42µs ± 2% 6.49µs ± 4% -12.48%
MatchAll/frog-4 1.56µs ± 1% 1.75µs ± 1% +12.33%
MatchAll/apple_frog-4 3.29µs ± 3% 3.63µs ± 1% +10.50%
MatchAll/apple_frog_chalk-4 5.24µs ± 0% 5.67µs ± 2% +8.11%
MatchAll/a_b_c_d_e_f_g_h_i_j_k… 37.5µs ± 3% 46.7µs ± 5% +24.46%
Match/#00-4 13.3ns ± 0% 13.9ns ± 0% +4.25%
Match/apple-4 1.43µs ± 2% 1.73µs ± 1% +20.50%
Match/ball-4 1.75µs ± 1% 1.73µs ± 1% -1.35%
Match/token-4 1.44µs ± 1% 1.73µs ± 1% +20.57%
Match/all_ball-4 3.67µs ± 1% 2.12µs ± 3% -42.23%
Match/all_green_ball-4 3.88µs ± 1% 2.17µs ± 1% -44.03%
Match/all_red_ball-4 3.72µs ± 1% 2.20µs ± 2% -40.96%
Match/all_small_ball-4 3.64µs ± 3% 2.21µs ± 2% -39.31%
Match/all_large_ball-4 3.62µs ± 2% 2.19µs ± 2% -39.63%
Match/apple_ball_chalk-4 1.70µs ± 1% 1.83µs ± 1% +7.27%
Match/apple_all_ball_chalk-4 1.72µs ± 3% 1.83µs ± 1% +6.57%
Match/frog-4 1.43µs ± 3% 1.69µs ± 1% +18.66%
Match/apple_frog-4 1.51µs ± 3% 1.71µs ± 1% +13.02%
Match/apple_frog_chalk-4 1.79µs ± 2% 1.85µs ± 1% +3.38%
Match/a_b_c_d_e_f_g_h_i_j_k_l… 1.71µs ± 4% 1.64µs ± 1% -3.99%
old new
name allocs/op allocs/op delta
MatchAll/#00-4 0.00 0.00 ~
MatchAll/apple-4 12.0 ± 0% 13.0 ± 0% +8.33%
MatchAll/ball-4 14.0 ± 0% 13.0 ± 0% -7.14%
MatchAll/token-4 12.0 ± 0% 13.0 ± 0% +8.33%
MatchAll/all_ball-4 24.0 ± 0% 13.0 ± 0% -45.83%
MatchAll/all_green_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
MatchAll/all_red_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
MatchAll/all_small_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
MatchAll/all_large_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
MatchAll/apple_ball_chalk-4 43.0 ± 0% 41.0 ± 0% -4.65%
MatchAll/apple_all_ball_chalk-4 49.0 ± 0% 41.0 ± 0% -16.33%
MatchAll/frog-4 11.0 ± 0% 13.0 ± 0% +18.18%
MatchAll/apple_frog-4 23.0 ± 0% 27.0 ± 0% +17.39%
MatchAll/apple_frog_chalk-4 36.0 ± 0% 41.0 ± 0% +13.89%
MatchAll/a_b_c_d_e_f_g_h_i_j_k… 261 ± 0% 363 ± 0% +39.08%
Match/#00-4 0.00 0.00 ~
Match/apple-4 12.0 ± 0% 13.0 ± 0% +8.33%
Match/ball-4 14.0 ± 0% 13.0 ± 0% -7.14%
Match/token-4 12.0 ± 0% 13.0 ± 0% +8.33%
Match/all_ball-4 24.0 ± 0% 13.0 ± 0% -45.83%
Match/all_green_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
Match/all_red_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
Match/all_small_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
Match/all_large_ball-4 25.0 ± 0% 13.0 ± 0% -48.00%
Match/apple_ball_chalk-4 13.0 ± 0% 13.0 ± 0% ~
Match/apple_all_ball_chalk-4 13.0 ± 0% 13.0 ± 0% ~
Match/frog-4 11.0 ± 0% 13.0 ± 0% +18.18%
Match/apple_frog-4 11.0 ± 0% 13.0 ± 0% +18.18%
Match/apple_frog_chalk-4 13.0 ± 0% 13.0 ± 0% ~
Match/a_b_c_d_e_f_g_h_i_j_k_l… 11.0 ± 0% 13.0 ± 0% +18.18%
There is one optimisation left that I would like to make to improve the
MatchAll function. Every time I try to implement it the code becomes a mess
again. Either that or performance takes a hit because of the setup and
bookkeeping involved. Still, I’m going to try one last time this evening and
if it doesn’t pan out leave it for now.
In the meantime the new code is out on the public dev branch.
--
Diddymus
Up to Main Index Up to Journal for June, 2019